1. Field of the Invention
The present general inventive concept relates to computer image processing, and more particularly, to systems and methods for digital image editing.
2. Description of the Related Art
Related art references to the general inventive concept are listed below and their content is incorporated herein by reference. Acknowledgement of the references as related art is not to be inferred as meaning that these are in any way relevant to the patentability of the general inventive concept disclosed herein. Each reference is identified by a number enclosed in square brackets and accordingly, each related art reference will be referred to throughout the specification by numbers enclosed in square brackets.    [1] A. Agarwala, M. Dontcheva, M. Agrawala, S. Drucker, A. Colburn, B. Curless, D. Salesin, and M. Cohen. Interactive digital photomontage. ACM Trans. Graph., 23(3):294-302, 2004.    [2] U.S. Pat. No. 7,477,800-Method for retargeting images, S. Avidan and A. Shamir.    [3] Y. Boykov, O. Veksler, and R. Zabih. Fast approximate energy minimization via graph cuts. IEEET-PAMI, 23:2001, 2001.    [4] T. Cho, M. Butman, S. Avidan, and W. Freeman. The patch transform and its applications to image editing. In CVPR'08, 2008.    [5] A. Criminisi, P. Prez, and K. Toyama. Object removal by exemplar-based inpainting. In CVPR'03, volume 2, pages 721-728, 2003.    [6] J. Hays and A. Efros. Scene completion using millions of photographs. CACM, 51(10):87-94, 2008.    [7] V. Kolmogorov and R. Zabih. What energy functions can be minimized via graph cuts? In ECCV'02, pages 65-81, 2002.    [8] N. Komodakis. Image completion using global optimization. In CVPR'06, pages 442-452, 2006.    [9] V. Kwatra, A. Schodl, I. Essa, G. Turk, and A. Bobick. Graphcut textures: image and video synthesis using graph cuts. In SIGGRAPH'03, pages 277-286, 2003.    [10]H. Lombaert, Y. Sun, L. Grady, and C. Xu. A multilevel banded graph cuts method for fast image segmentation. In ICCV'05, volume 1, pages 259-265, 2005.    [11] M. Rubinstein, A. Shamir, and S. Avidan. Improved seam carving for video retargeting. ACM Trans. Graph., 27(3):1-9, 2008.    [12] D. Simakov, Y. Caspi, E. Shechtman, and M. Irani. Summarizing visual data using bidirectional similarity. In CVPR'08, 2008.    [13] J. Sun, L. Yuan, J. Jia, and H. Shum. Image completion with structure propagation. In SIGGRAPH'05, pages 861-868, 2005.    [14] Y. Wang, C. Tai, O. Sorkine, and T. Lee. Optimized scale-and-stretch for image resizing. ACMTrans. Graph., 27(5):1-8, 2008.    [15] Y. Wexler, E. Shechtman, and M. Irani. Space-time video completion. CVPR'04, 1:120-127, 2004.    [16] M. Wilczkowiak, G. J. Brostow, B. Tordoff, and R. Cipolla. Hole filling through photomontage.    [17] L. Wolf, M. Guttmann, and D. Cohen-Or. Non-homogeneous content-driven video-retargeting. In ICCV'07, 2007.    [18] U.S. Pat. No. 7,529,429, Auto collage. Rother, C., Bordeaux, L., Hamadi, Y., and Blake, A.    [19] A. Hertzmann, C. Jacobs, N. Oliver, B. Curless, and D. Salesin. Image analogies. In SIGGRAPH 2001, pp. 327-340.    [20] W. Freeman, T. Jones, and E. Pasztor, Example-based super-resolution. IEEE Computer Graphics and Applications vol. 22, no. 2, pp. 56-65. 2002.    [21] D. Glasner, S. Bagon, and M. Irani. 2009. Super-resolution from a single image. In ICCV 2009.    [22] C. Bishop, Pattern Recognition and Machine Learning. Springer, 2006.
Geometric image rearrangement is becoming more popular as it is being enabled by recent computer vision technologies. While early manipulations included mostly crop and scale, modern tools enable smart photomontage [1], image resizing (a.k.a. “retargeting”) [2, 11, 17, 12, 14], object rearrangement and removal [4, 12, 5], etc. Recent retargeting methods propose effective resizing by examining image content and removing “less important” regions. Seam carving [2, 11] performs retargeting by iterative removal of narrow curves from the image. As an iterative greedy algorithm no global optimization can be made, and something as simple as removing one of several similar objects is impossible. Since seam carving removes regions having low gradients, significant distortions occur when most image regions have many gradients.
A continuous image warping was proposed in [17, 14]. While those methods provide global considerations, continuous warping can introduce significant distortions. Also, good object removal is almost impossible using a continuous warping. Both methods use saliency maps (e.g. face detection), and saliency mistakes may cause distorted results.
An approach based on bidirectional similarity is presented in [12], which also names retargeting as “summarization”. Every feature in the input should appear in the output, and every feature in the output should appear in the input. This method can also be used for image rearrangement. This method is computationally intensive, and while the bidirectional similarity may indeed be important for summarization, it may not be essential for retargeting or other editing related tasks.
In patch transform [4], the image is segmented into patches which are than rearranged using global optimization. The need for prior determination of the patch size is a major drawback of this method. Also, the patches reduce significantly the flexibility for rearrangement and composition. The inherent problems of using patches are also affecting the object removal in [8]. We found that our results, moving individual pixels, significantly improve the results in [4].
An approach of processing images by example is “Image-Analogies” [19]. Their synthesis framework involves two stages: (i) A design stage, whose input includes two sample images, where one image is a filtered version of the other. This stage learns the associated filter. (ii) An application stage, in which the learned filter is applied to a new target image in order to create an analogous filtered result. The second stage includes searching for patches in the unfiltered sample image that are similar to patches in the target image, and their corresponding patches in the filtered sample image are copied into the output image. Note that if the two sample images are identical, the filter is the identity transformation, and this algorithm performs a texture transfer of the sample image into the target image. Example based super-resolution was introduced by [20], who use a database of similar images to create a super-resolution version of a given image. Super-resolution based on self similarity was recently proposed by [21]. In this work similarity between patches within the same scale and across scales is used for computing the magnified image. Their results are comparable to those of [20], suggesting that the information in the original image may be more useful than information from other images with similar textures.